
#include <vector>
#include "Edge.h"
#include "BellmanFordTest.h"
#include "DijkstraTest.h"
#include "FloydWarshallTest.h"
#include "JohnsonTest.h"
#include "Generator.h"

#include <iostream>
#include <iomanip>

using namespace std;
using namespace zbp;
using namespace boost;

bool bellman_ford(int s, int* d, int* p, vector<Edge> e, int *weights, int nodes_count, int edge_count);
double bellman_ford_boost_test1(int source_vertex, BoostEdge* edge_array, int* weights, int nodes_count, int edges_count, bool display);


int main32()
{
	int nodes_count = 10;
	int adjacent_count = 5;
	int negative_count = 1000000000;
	int max_weight = 10000;

	SimpleGraph simple_graph;
	CompleteGraph<int> complete_graph(nodes_count);

	BoostEdge* boost_edges = new BoostEdge[nodes_count * adjacent_count];
	int* boost_weights = new int[nodes_count * adjacent_count];	
	
	zbp::Generator g;
	g.generate_graph(simple_graph, complete_graph, boost_edges, boost_weights, nodes_count, adjacent_count, max_weight, negative_count);

	int * d = new int[nodes_count];
	int *p = new int[nodes_count];
	
	for (int i = 0; i < nodes_count; i++)
	{
		d[i] = INT_MAX;
		p[i] = 0;
	}
	vector<Edge> e;
	for (int i = 0; i < nodes_count * adjacent_count; i++)
	{
		Edge e1(boost_edges[i].first,boost_edges[i].second,boost_weights[i]);
		e.push_back(e1);
	}
	
	clock_t ticks = clock();
	bellman_ford(1,d,p,e,boost_weights,nodes_count, nodes_count * adjacent_count);
	ticks = clock() - ticks;	
	double msec = (double)ticks / CLOCKS_PER_SEC * 1000;
	cout << "Time in ms moj: " << msec << endl << endl;
	
	for (int i = 0; i< nodes_count; i++)
		cout << d[i] << " ";
	cout << endl;
	
	bellman_ford_boost_test1(1, boost_edges, boost_weights, nodes_count, nodes_count*adjacent_count, true);
	return 0;
}

double bellman_ford_boost_test1(int source_vertex, BoostEdge* edge_array, int* weights, int nodes_count, int edges_count, bool display)
{	   	  	  	  	  	  	  	  
	typedef adjacency_list < vecS, vecS, directedS,
		no_property, EdgeProperties> Graph;
	#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
		// VC++ can't handle the iterator constructor
		Graph g(nodes_count);
		for (std::size_t j = 0; j < n_edges; ++j)
			add_edge(edge_array[j].first, edge_array[j].second, g);
	#else
		Graph g(edge_array, edge_array + edges_count, nodes_count);
	#endif
	graph_traits < Graph >::edge_iterator ei, ei_end;
	property_map<Graph, int EdgeProperties::*>::type 
	weight_pmap = get(&EdgeProperties::weight, g);
	int i = 0;
	for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei, ++i)
		weight_pmap[*ei] = weights[i];

	std::vector<int> distance(nodes_count, (std::numeric_limits < short >::max)());
	std::vector<std::size_t> parent(nodes_count);
	for (i = 0; i < nodes_count; ++i)
		parent[i] = i;

	distance[source_vertex] = 0;

	clock_t ticks = clock();

	#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
		bool result = bellman_ford_shortest_paths
			(g, int(nodes_count), weight_pmap, &parent[0], &distance[0], 
			closed_plus<int>(), std::less<int>(), default_bellman_visitor());
	#else
		bool result = bellman_ford_shortest_paths
			(g, int (nodes_count), weight_map(weight_pmap).distance_map(&distance[0]).
			predecessor_map(&parent[0]));
	#endif	 

	ticks = clock() - ticks;	
	double msec = (double)ticks / CLOCKS_PER_SEC * 1000;

	if (display)
	{
		cout << "Boost: bellman_ford_shortest_paths function for node " << source_vertex << endl << endl;

		if (result)
		{
			display_vector(distance, std::numeric_limits<int>::max());	
		}
		else
		{
			cout << "Negative weight found." << endl;
		}

		cout << "Time in ms: " << msec << endl << endl;
	}

	return msec;
}

bool bellman_ford(int s, int* d, int* p, vector<Edge> e, int *weights, int nodes_count, int edge_count)
{
	int i, j;			
	
	d[s] = 0;
	vector<Edge>::iterator it;
	for (i = 0; i < nodes_count - 1 ; i++)
	{
		bool at_least_one_edge_relaxed = false;
		for (it = e.begin(); it != e.end() ; it++)
		{					
			if (d[(*it).coord.first] + (*it).weight < d[(*it).coord.second])
			{
				at_least_one_edge_relaxed = true;
				d[(*it).coord.second] = d[(*it).coord.first] + (*it).weight;
				p[(*it).coord.second] = (*it).coord.first;
			}
		}
		if (!at_least_one_edge_relaxed)
        break;
	}


	/*for (i = 0; i < edge_count; i++)
	{				
		if (d[e[i].second] > d[e[i].first] + weights[i])
		{
			return false;
		}	
	}*/

	return true;
}
